﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0089_LongestPalindrome : IAlgorithm
    {
        // 5. 最长回文子串

        // 给你一个字符串 s，找到 s 中最长的回文子串。

        // 提示：
        //  1 <= s.length <= 1000
        //  s 仅由数字和英文字母（大写和/或小写）组成

        public void Test()
        {
            // 算法参数定义
            string s = "cbbd";
            // 算法执行与打印
            Console.WriteLine(LongestPalindrome(s));
        }

        // 算法
        public string LongestPalindrome(string s)
        {
            int start = 0, end = 0;
            for (int i = 0; i < s.Length; i++)
            {
                int len1 = ExpandAroundCenter(s, i, i);
                int len2 = ExpandAroundCenter(s, i, i + 1);
                int len = Math.Max(len1, len2);
                if (len > end - start)
                {
                    start = i - (len - 1) / 2;
                    end = i + len / 2;
                }
            }
            return s[start..(end + 1)];
        }
        public int ExpandAroundCenter(string s, int left, int right)
        {
            while (left >= 0 && right < s.Length && s[left] == s[right])
            {
                --left;
                ++right;
            }
            return right - left - 1;
        }
    }
}
